package leetcode.code0355;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class Twitter {
	class Message {
		int sequence;// 消息序号，用以从近到远获得消息的排序
		int tweetId;// 添加到结果集
		Message next;// 上一条消息，逻辑上的上一条消息，在链表的next上记录

		public Message() {
		}

		public Message(int sequence, int tweetId) {
			this.sequence = sequence;
			this.tweetId = tweetId;
		}

		// 插入一个新的推文
		public void addMsg(Message newMsg) {
			newMsg.next = this.next;
			this.next = newMsg;
		}

	}

	Message[] userMsg;// 所有人的推文列表，从近到远的单链表

	static int MAX = 501;// 最多500人用数组替代HashMap

	Map<Integer, Set<Integer>> follow;// Map<用户A的id,用户A关注的人的集合>

	int sequence;// 消息序号

	public Twitter() {
		userMsg = new Message[MAX];
		follow = new HashMap<>();
		for (int i = 1; i < MAX; i++) {
			userMsg[i] = new Message();// 初始化头节点，空消息
			Set<Integer> set = new HashSet<>();
			set.add(i);// 别忘了加自己，自己发文也是结果集的一部分
			follow.put(i, set);// 初始化关注集合
		}
		sequence = 0;// 消息序号
	}

	public void postTweet(int userId, int tweetId) {
		Message newMsg = new Message(this.sequence++, tweetId);// 创建新的推文
		userMsg[userId].addMsg(newMsg);// 放到用户的推文列表头部。
	}

	public List<Integer> getNewsFeed(int userId) {
		Set<Integer> f = follow.get(userId);
		// 所有被关注人的最新推文，按照从近到远，即sequence的从大到小排列
		PriorityQueue<Message> pq = new PriorityQueue<>((a, b) -> b.sequence - a.sequence);
		for (Integer followeeId : f) {
			Message msg = userMsg[followeeId];
			if (msg.next != null) {
				pq.add(msg.next);// 有推文的添加到大根堆中
			}
		}
		int size = 10;
		List<Integer> ans = new ArrayList<>();
		while (size > 0 && !pq.isEmpty()) {
			Message msg = pq.poll();
			ans.add(msg.tweetId);
			size--;
			if (msg.next != null) {
				pq.add(msg.next);// 背取走推文的人，如果还有推文，添加到大根堆中
			}
		}
		return ans;
	}

	public void follow(int followerId, int followeeId) {
		Set<Integer> f = follow.get(followerId);
		f.add(followeeId);// followerId的关注人集合增加followeeId
		follow.put(followerId, f);
	}

	public void unfollow(int followerId, int followeeId) {
		Set<Integer> f = follow.get(followerId);
		if (f.contains(followeeId)) {
			f.remove(followeeId);// followerId的关注人集合移除followeeId
			follow.put(followerId, f);
		}
	}

	public static void main(String[] args) {
		Twitter twitter = new Twitter();
		twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
		twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
		twitter.follow(1, 2); // 用户 1 关注了用户 2
		twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
		twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5
								// 之后发送的
		twitter.unfollow(1, 2); // 用户 1 取消关注了用户 2
		twitter.getNewsFeed(1); // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
	}

}
